package MonotonicStack;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author Lzm
 * @version 1.0
 */
public class dailyTemperatures_ {
  @Test
  public void dailyTemperaturesTest(){
    int[] temperatures = new int[]{73,74,75,71,69,72,76,73};
    //int[] temperatures = new int[]{30,40,50,60};
    int[] ints = dailyTemperatures(temperatures);
    for (int anInt : ints) {
      System.out.println(anInt);
    }

  }


  /*public int[] dailyTemperatures(int[] temperatures) {
    if (temperatures.length == 1){
      return new int[]{0};
    }

    int[] result = new int[temperatures.length];
    for (int left = 0 ; left < temperatures.length ; left++){
      for (int right = left + 1 ; right < temperatures.length ; right++){
        if (temperatures[left] < temperatures[right]){
          result[left] = right - left;
          break;
        }
      }
    }
    return result;
  }*/
  // 利用单调栈来解决此类问题, 时间复杂度为O(n)
  /**
   * @param temperatures:
   * @return int
   * @author 25859
   * @description TODO
   * @date 2025/8/14 18:37
   *
   *
   * 以{73,74,75,71,69,72,76,73}为例
   * 第一次 stack将下标0压入栈中
   * for循环从1开始遍历数组,
   * 如果当前元素大于栈顶下标元素时, 将栈顶元素弹出, 将当前元素的数组下标压入栈中, result[原栈顶] = 当前元素下标 - 原栈顶下标
   * 如果当前元素小于或等于栈顶下标元素时, 就将当前元素压入栈中
   * 如果遍历结束后, 栈不为空, 则将栈都弹出, 令result[栈下标] = 0
   */
  public int[] dailyTemperatures(int[] temperatures) {
    if (temperatures.length == 1){
      return new int[]{0};
    }
    int[] result = new int[temperatures.length];
    Stack<Integer> stack = new Stack<>();
    stack.push(0);
    for (int i = 1 ; i < temperatures.length ; i++){
      //判断当前元素于栈顶下标元素的大小
      // 用while是因为如果当前元素比栈顶下标元素大的话, 也有可能比栈中其他下标元素也大, 所以用while
      while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]){
        result[stack.peek()] = i - stack.peek();
        stack.pop();
      }
        stack.push(i);
    }
    //若栈不为空
    while(!stack.isEmpty()) result[stack.pop()] = 0;
    return result;
  }
}
